Valid perfect square

Time: O(LogN); Space: O(1); medium

Given a positive integer num, write a function which returns True if num is a perfect square else False.

Follow up:

  • Do not use any built-in library function such as sqrt.

Example 1:

Input: num = 16

Output: True

Explanation:

  • sqrt(16) = 4

Example 2:

Input: num = 15

Output: False

Explanation:

  • sqrt(15) = 3.87

Constraints:

  • 1 <= num <= 2^31 - 1

1. Binary Search [O(LogN), O(1)]

[1]:

class Solution1(object):
    """
    Time: O(LogN)
    Space: O(1)
    """
    def isPerfectSquare(self, num):
        """
        :type num: int
        :rtype: bool
        """
        left, right = 1, num

        while left <= right:
            mid = left + (right - left) // 2
            if mid >= num / mid:
                right = mid - 1
            else:
                left = mid + 1

        return left == num // left and num % left == 0

[2]:

s = Solution1()

num = 16
assert s.isPerfectSquare(num) == True

num = 15
assert s.isPerfectSquare(num) == False